<!DOCTYPE html>
<html lang="zh-cn" dir="ltr">
    <head><script src="/livereload.js?mindelay=10&amp;v=2&amp;port=1313&amp;path=livereload" data-no-instant defer></script><meta charset='utf-8'>
<meta name='viewport' content='width=device-width, initial-scale=1'><meta name='description' content="洛谷刷题随记">
<title>数据结构算法积累</title>

<link rel='canonical' href='http://localhost:1313/p/suanfa/'>

<link rel="stylesheet" href="/scss/style.min.663803bebe609202d5b39d848f2d7c2dc8b598a2d879efa079fa88893d29c49c.css"><meta property='og:title' content="数据结构算法积累">
<meta property='og:description' content="洛谷刷题随记">
<meta property='og:url' content='http://localhost:1313/p/suanfa/'>
<meta property='og:site_name' content='VenKing_Ryao的个人博客'>
<meta property='og:type' content='article'><meta property='article:section' content='Post' /><meta property='article:published_time' content='2024-11-24T00:00:00&#43;00:00'/><meta property='article:modified_time' content='2024-11-24T00:00:00&#43;00:00'/><meta property='og:image' content='http://localhost:1313/images/studying1.jpg' />
<meta name="twitter:title" content="数据结构算法积累">
<meta name="twitter:description" content="洛谷刷题随记"><meta name="twitter:card" content="summary_large_image">
    <meta name="twitter:image" content='http://localhost:1313/images/studying1.jpg' />
    <link rel="shortcut icon" href="/favicon.ico" />

  


    </head>
    <body class="
    article-page
    ">
    <script>
        (function() {
            const colorSchemeKey = 'StackColorScheme';
            if(!localStorage.getItem(colorSchemeKey)){
                localStorage.setItem(colorSchemeKey, "auto");
            }
        })();
    </script><script>
    (function() {
        const colorSchemeKey = 'StackColorScheme';
        const colorSchemeItem = localStorage.getItem(colorSchemeKey);
        const supportDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches === true;

        if (colorSchemeItem == 'dark' || colorSchemeItem === 'auto' && supportDarkMode) {
            

            document.documentElement.dataset.scheme = 'dark';
        } else {
            document.documentElement.dataset.scheme = 'light';
        }
    })();
</script>
<div class="container main-container flex on-phone--column extended"><aside class="sidebar left-sidebar sticky ">
    <button class="hamburger hamburger--spin" type="button" id="toggle-menu" aria-label="切换菜单">
        <span class="hamburger-box">
            <span class="hamburger-inner"></span>
        </span>
    </button>

    <header>
        
            
            <figure class="site-avatar">
                <a href="/">
                
                    
                    
                    
                        
                        <img src="/img/avatar_hu12578812116692384380.png" width="300"
                            height="300" class="site-logo" loading="lazy" alt="Avatar">
                    
                
                </a>
                
                    <span class="emoji">🤔</span>
                
            </figure>
            
        
        
        <div class="site-meta">
            <h1 class="site-name"><a href="/">VenKing_Ryao的个人博客</a></h1>
            <h2 class="site-description">无限进步</h2>
        </div>
    </header><ol class="menu-social">
            
                <li>
                    <a 
                        href='https://github.com/RyaoVen'
                        target="_blank"
                        title="GitHub"
                        rel="me"
                    >
                        
                        
                            <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-brand-github" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z" fill="none"/>
  <path d="M9 19c-4.3 1.4 -4.3 -2.5 -6 -3m12 5v-3.5c0 -1 .1 -1.4 -.5 -2c2.8 -.3 5.5 -1.4 5.5 -6a4.6 4.6 0 0 0 -1.3 -3.2a4.2 4.2 0 0 0 -.1 -3.2s-1.1 -.3 -3.5 1.3a12.3 12.3 0 0 0 -6.2 0c-2.4 -1.6 -3.5 -1.3 -3.5 -1.3a4.2 4.2 0 0 0 -.1 3.2a4.6 4.6 0 0 0 -1.3 3.2c0 4.6 2.7 5.7 5.5 6c-.6 .6 -.6 1.2 -.5 2v3.5" />
</svg>



                        
                    </a>
                </li>
            
                <li>
                    <a 
                        href='https://twitter.com'
                        target="_blank"
                        title="Twitter"
                        rel="me"
                    >
                        
                        
                            <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-brand-twitter" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z" fill="none"/>
  <path d="M22 4.01c-1 .49 -1.98 .689 -3 .99c-1.121 -1.265 -2.783 -1.335 -4.38 -.737s-2.643 2.06 -2.62 3.737v1c-3.245 .083 -6.135 -1.395 -8 -4c0 0 -4.182 7.433 4 11c-1.872 1.247 -3.739 2.088 -6 2c3.308 1.803 6.913 2.423 10.034 1.517c3.58 -1.04 6.522 -3.723 7.651 -7.742a13.84 13.84 0 0 0 .497 -3.753c-.002 -.249 1.51 -2.772 1.818 -4.013z" />
</svg>



                        
                    </a>
                </li>
            
        </ol><ol class="menu" id="main-menu">
        
        
        
        <li >
            <a href='/' >
                
                
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-home" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <polyline points="5 12 3 12 12 3 21 12 19 12" />
  <path d="M5 12v7a2 2 0 0 0 2 2h10a2 2 0 0 0 2 -2v-7" />
  <path d="M9 21v-6a2 2 0 0 1 2 -2h2a2 2 0 0 1 2 2v6" />
</svg>



                
                <span>主页</span>
            </a>
        </li>
        
        
        <li >
            <a href='/%E5%85%B3%E4%BA%8E/' >
                
                
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-user" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="7" r="4" />
  <path d="M6 21v-2a4 4 0 0 1 4 -4h4a4 4 0 0 1 4 4v2" />
</svg>



                
                <span>关于</span>
            </a>
        </li>
        
        
        <li >
            <a href='/archives/' >
                
                
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-archive" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <rect x="3" y="4" width="18" height="4" rx="2" />
  <path d="M5 8v10a2 2 0 0 0 2 2h10a2 2 0 0 0 2 -2v-10" />
  <line x1="10" y1="12" x2="14" y2="12" />
</svg>



                
                <span>归档</span>
            </a>
        </li>
        
        
        <li >
            <a href='/search/' >
                
                
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-search" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="10" cy="10" r="7" />
  <line x1="21" y1="21" x2="15" y2="15" />
</svg>



                
                <span>搜索</span>
            </a>
        </li>
        
        
        <li >
            <a href='/%E7%9B%B8%E5%85%B3%E8%B6%85%E9%93%BE%E6%8E%A5/' >
                
                
                
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-link" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M10 14a3.5 3.5 0 0 0 5 0l4 -4a3.5 3.5 0 0 0 -5 -5l-.5 .5" />
  <path d="M14 10a3.5 3.5 0 0 0 -5 0l-4 4a3.5 3.5 0 0 0 5 5l.5 -.5" />
</svg>



                
                <span>相关超链接</span>
            </a>
        </li>
        
        <li class="menu-bottom-section">
            <ol class="menu">
                    
                        <li id="i18n-switch">  
                            <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-language" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z" fill="none"/>
  <path d="M4 5h7" />
  <path d="M9 3v2c0 4.418 -2.239 8 -5 8" />
  <path d="M5 9c-.003 2.144 2.952 3.908 6.7 4" />
  <path d="M12 20l4 -9l4 9" />
  <path d="M19.1 18h-6.2" />
</svg>



                            <select name="language" title="language" onchange="window.location.href = this.selectedOptions[0].value">
                                
                                    <option value="http://localhost:1313/en/" >English</option>
                                
                                    <option value="http://localhost:1313/" selected>简体中文</option>
                                
                            </select>
                        </li>
                    
                

                
                    <li id="dark-mode-toggle">
                        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-toggle-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="8" cy="12" r="2" />
  <rect x="2" y="6" width="20" height="12" rx="6" />
</svg>



                        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-toggle-right" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="16" cy="12" r="2" />
  <rect x="2" y="6" width="20" height="12" rx="6" />
</svg>



                        <span>暗色模式</span>
                    </li>
                
            </ol>
        </li>
    </ol>
</aside>

    <aside class="sidebar right-sidebar sticky">
        
            
                
    <section class="widget archives">
        <div class="widget-icon">
            <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <line x1="5" y1="9" x2="19" y2="9" />
  <line x1="5" y1="15" x2="19" y2="15" />
  <line x1="11" y1="4" x2="7" y2="20" />
  <line x1="17" y1="4" x2="13" y2="20" />
</svg>



        </div>
        <h2 class="widget-title section-title">目录</h2>
        
        <div class="widget--toc">
            <nav id="TableOfContents">
  <ol>
    <li><a href="#画饼-缓慢更新中可以催更">画饼 （缓慢更新中，可以催更）</a>
      <ol>
        <li><a href="#数据结构">数据结构：</a></li>
        <li><a href="#算法">算法：</a></li>
        <li><a href="#更复杂的数据结构">更复杂的数据结构：</a></li>
        <li><a href="#高级算法技巧">高级算法技巧：</a></li>
      </ol>
    </li>
    <li><a href="#查找">查找</a>
      <ol>
        <li><a href="#二分查找">二分查找</a></li>
      </ol>
    </li>
    <li><a href="#动态规划臭名昭著的dp">动态规划(<del>臭名昭著的</del>DP)</a></li>
    <li><a href="#数组">数组</a>
      <ol>
        <li><a href="#差分法">差分法</a></li>
        <li><a href="#前缀法">前缀法</a></li>
      </ol>
    </li>
  </ol>
</nav>
        </div>
    </section>

            
        
    </aside>


            <main class="main full-width">
    <article class="has-image main-article">
    <header class="article-header">
        <div class="article-image">
            <a href="/p/suanfa/">
                
                    <img src="/images/studying1.jpg" loading="lazy" alt="Featured image of post 数据结构算法积累" />
                
            </a>
        </div>
    

    <div class="article-details">
    
    <header class="article-category">
        
            <a href="/categories/%E7%AC%94%E8%AE%B0/" >
                笔记
            </a>
        
            <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" >
                数据结构
            </a>
        
            <a href="/categories/ryao_venking/" >
                Ryao_VenKing
            </a>
        
    </header>
    

    <div class="article-title-wrapper">
        <h2 class="article-title">
            <a href="/p/suanfa/">数据结构算法积累</a>
        </h2>
    
        
        <h3 class="article-subtitle">
            洛谷刷题随记
        </h3>
        
    </div>

    
    
    
    
    <footer class="article-time">
        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M11.795 21h-6.795a2 2 0 0 1 -2 -2v-12a2 2 0 0 1 2 -2h12a2 2 0 0 1 2 2v4" />
  <circle cx="18" cy="18" r="4" />
  <path d="M15 3v4" />
  <path d="M7 3v4" />
  <path d="M3 11h16" />
  <path d="M18 16.496v1.504l1 1" />
</svg>
                <time class="article-time--published">Nov 24, 2024</time>
            </div>
        

        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



                <time class="article-time--reading">
                    阅读时长: 2 分钟
                </time>
            </div>
        
    </footer>
    

    
</div>

</header>

    <section class="article-content">
    
    
    <p>本质上算法只是一种思维方式，语言只是其载体，是故用任何语言积累数据结构都可以。因此笔者便不统一书写语言了，将写题时的随笔记下，也随便督促读者去多学点基础语法知识，毕竟技多不压身，能多学一点总是好的。</p>
<h2 id="画饼-缓慢更新中可以催更">画饼 （缓慢更新中，可以催更）
</h2><p>基础的数据结构和算法是计算机科学中的核心概念，以下是一些常见的数据结构和算法分类：</p>
<h3 id="数据结构">数据结构：
</h3><ol>
<li><strong>数组（Array）</strong>：一种基础的数据结构，用于存储一系列相同类型的数据。</li>
<li><strong>链表（Linked List）</strong>：
<ul>
<li>单链表</li>
<li>双链表</li>
<li>循环链表</li>
</ul>
</li>
<li><strong>栈（Stack）</strong>：后进先出（LIFO）的数据结构。</li>
<li><strong>队列（Queue）</strong>：先进先出（FIFO）的数据结构。
<ul>
<li>循环队列</li>
<li>双端队列（Deque）</li>
</ul>
</li>
<li><strong>树（Tree）</strong>：
<ul>
<li>二叉树</li>
<li>平衡二叉树（AVL树）</li>
<li>红黑树</li>
<li>B树、B+树</li>
<li>堆（Heap）</li>
</ul>
</li>
<li><strong>图（Graph）</strong>：
<ul>
<li>有向图</li>
<li>无向图</li>
<li>加权图</li>
<li>连通图</li>
</ul>
</li>
<li><strong>哈希表（Hash Table）</strong>：通过哈希函数实现快速查找的数据结构。</li>
<li><strong>集合（Set）</strong>：一种抽象数据类型，用于存储无序且不重复的元素。</li>
<li><strong>字典（Dictionary）/映射（Map）</strong>：一种抽象数据类型，用于存储键值对。</li>
</ol>
<h3 id="算法">算法：
</h3><ol>
<li>
<p><strong>排序算法</strong>：</p>
<ul>
<li>冒泡排序</li>
<li>选择排序</li>
<li>插入排序</li>
<li>快速排序</li>
<li>归并排序</li>
<li>堆排序</li>
<li>希尔排序</li>
<li>计数排序</li>
<li>基数排序</li>
</ul>
</li>
<li>
<p><strong>搜索算法</strong>：</p>
<ul>
<li>顺序搜索</li>
<li>二分搜索</li>
<li>深度优先搜索（DFS）</li>
<li>广度优先搜索（BFS）</li>
<li>A*搜索</li>
<li>贪心搜索</li>
</ul>
</li>
<li>
<p><strong>字符串匹配算法</strong>：</p>
<ul>
<li>朴素字符串匹配</li>
<li>KMP算法</li>
<li>Rabin-Karp算法</li>
<li>Boyer-Moore算法</li>
</ul>
</li>
<li>
<p><strong>图算法</strong>：</p>
<ul>
<li>拓扑排序</li>
<li>最短路径算法（Dijkstra、Bellman-Ford、Floyd-Warshall）</li>
<li>最小生成树算法（Prim、Kruskal）</li>
</ul>
</li>
</ol>
<h3 id="更复杂的数据结构">更复杂的数据结构：
</h3><ol>
<li><strong>跳表（Skip List）</strong>：用于快速查找的有序数据结构，可以看作是多层链表的结合。</li>
<li><strong>并查集（Union-Find）</strong>：一种数据结构，用于处理一些不交集的合并及查询问题。</li>
<li><strong>线段树（Segment Tree）</strong>：用于高效解决区间查询和更新问题。</li>
<li><strong>树状数组（Binary Indexed Tree）/斐波那契堆（Fibonacci Heap）</strong>：用于高效处理范围查询和动态修改的问题。</li>
<li><strong>Trie（前缀树）</strong>：用于高效地存储和检索字符串数据集中的键。</li>
<li><strong>布隆过滤器（Bloom Filter）</strong>：一种空间效率极高的数据结构，用于测试一个元素是否属于集合，有可能会出现误判。</li>
<li><strong>LSM树（Log-Structured Merge-Tree）</strong>：通常用于键值存储系统中，例如LevelDB和Cassandra。</li>
<li><strong>倒排索引（Inverted Index）</strong>：常用于全文搜索引擎，如Elasticsearch和Solr。</li>
</ol>
<h3 id="高级算法技巧">高级算法技巧：
</h3><ol>
<li>
<p><strong>分治算法（Divide and Conquer）</strong>：将问题分解成若干个小问题递归求解，然后再合并结果。</p>
</li>
<li>
<p><strong>动态规划（Dynamic Programming）</strong>：</p>
<ul>
<li>斐波那契数列</li>
<li>最长公共子序列（LCS）</li>
<li>最长递增子序列（LIS）</li>
<li>0-1背包问题</li>
<li>编辑距离（Levenshtein距离）</li>
</ul>
</li>
<li>
<p><strong>贪心算法（Greedy Algorithms）</strong>：</p>
<ul>
<li>最小生成树（Prim、Kruskal）</li>
<li>哈夫曼编码</li>
</ul>
</li>
<li>
<p><strong>回溯算法（Backtracking）</strong>：</p>
<ul>
<li>N皇后问题</li>
<li>子集和问题</li>
<li>组合问题</li>
</ul>
</li>
<li>
<p><strong>分支限界法（Branch and Bound）</strong>：</p>
<ul>
<li>旅行商问题（TSP）</li>
<li>零一背包问题</li>
</ul>
</li>
<li>
<p><strong>启发式算法（Heuristic Algorithms）</strong>：</p>
<ul>
<li>A*搜索算法</li>
<li>蚁群优化（ACO）</li>
<li>粒子群优化（PSO）</li>
</ul>
</li>
<li>
<p><strong>随机化算法（Randomized Algorithms）</strong>：</p>
<ul>
<li>蒙特卡洛算法</li>
<li>拉斯维加斯算法</li>
<li>跳跃表</li>
</ul>
</li>
<li>
<p><strong>近似算法（Approximation Algorithms）</strong>：</p>
<ul>
<li>用于在多项式时间内找到近似最优解的算法，适用于NP难问题。</li>
</ul>
</li>
<li>
<p><strong>流算法（Streaming Algorithms）</strong>：</p>
<ul>
<li>用于处理大量数据流的算法，通常只需要一次或几次数据遍历。</li>
</ul>
</li>
<li>
<p><strong>字符串匹配算法</strong>：</p>
<ul>
<li>后缀数组</li>
<li>后缀树</li>
<li>正则表达式匹配</li>
</ul>
</li>
</ol>
<h2 id="查找">查找
</h2><p>通常的，在我们需要进行查找时，使用遍历查找一个一个检查过去便能满足我们的需求，在数据量很小时使用其他的方法甚至会使代码的时间复杂度上升，但当我们处理大数据量时，遍历的效率过于低下，因此我们需要一些特殊的方法进行查找：</p>
<h3 id="二分查找">二分查找
</h3><p>二分查找的核心思路是高中数学中的二分法，每次取范围的百分之50，可以快速锁定目标数据所处区间。</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span><span class="lnt">32
</span><span class="lnt">33
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-c++" data-lang="c++"><span class="line"><span class="cl"><span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp">
</span></span></span><span class="line"><span class="cl"><span class="cp">#include</span> <span class="cpf">&lt;vector&gt;</span><span class="cp">
</span></span></span><span class="line"><span class="cl"><span class="cp"></span>
</span></span><span class="line"><span class="cl"><span class="c1">// 二分查找函数
</span></span></span><span class="line"><span class="cl"><span class="c1">// 参数：
</span></span></span><span class="line"><span class="cl"><span class="c1">// nums - 有序数组
</span></span></span><span class="line"><span class="cl"><span class="c1">// target - 要查找的目标值
</span></span></span><span class="line"><span class="cl"><span class="c1">// 返回值：
</span></span></span><span class="line"><span class="cl"><span class="c1">// 目标值在数组中的索引，如果未找到则返回-1
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="kt">int</span> <span class="nf">binarySearch</span><span class="p">(</span><span class="k">const</span> <span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">target</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">    <span class="kt">int</span> <span class="n">left</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>        <span class="c1">// 查找范围的左边界
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>    <span class="kt">int</span> <span class="n">right</span> <span class="o">=</span> <span class="n">nums</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="c1">// 查找范围的右边界
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>
</span></span><span class="line"><span class="cl">    <span class="k">while</span> <span class="p">(</span><span class="n">left</span> <span class="o">&lt;=</span> <span class="n">right</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// 当左边界小于等于右边界时继续查找
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>        <span class="kt">int</span> <span class="n">mid</span> <span class="o">=</span> <span class="n">left</span> <span class="o">+</span> <span class="p">(</span><span class="n">right</span> <span class="o">-</span> <span class="n">left</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span> <span class="c1">// 计算中间位置，避免直接相加可能导致的溢出
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>
</span></span><span class="line"><span class="cl">        <span class="k">if</span> <span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">mid</span><span class="p">]</span> <span class="o">==</span> <span class="n">target</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="c1">// 如果中间位置的元素等于目标值，返回中间位置的索引
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>            <span class="k">return</span> <span class="n">mid</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">mid</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">target</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="c1">// 如果中间位置的元素小于目标值，将左边界设置为中间位置加一
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>            <span class="c1">// 因为中间位置的元素已经不可能是目标值了，所以可以排除这部分
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>            <span class="n">left</span> <span class="o">=</span> <span class="n">mid</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">            <span class="c1">// 如果中间位置的元素大于目标值，将右边界设置为中间位置减一
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>            <span class="c1">// 同样，中间位置的元素已经不可能是目标值了，排除这部分
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>            <span class="n">right</span> <span class="o">=</span> <span class="n">mid</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        <span class="p">}</span>
</span></span><span class="line"><span class="cl">    <span class="p">}</span>
</span></span><span class="line"><span class="cl">
</span></span><span class="line"><span class="cl">    <span class="c1">// 如果循环结束仍未找到目标值，返回-1
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>    <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span>
</span></span></code></pre></td></tr></table>
</div>
</div><p>简而言之，二分查找的思路如下：首先确定查找范围的边界，然后取中间值并与目标值比较，然后将边界迁移至目标值所在的范围内，重复以下操作，以最终确定目标值的位置。
<code>注：二分查找的前提是所有元素有序排列。</code></p>
<h2 id="动态规划臭名昭著的dp">动态规划(<del>臭名昭著的</del>DP)
</h2><h2 id="数组">数组
</h2><p>计算机与数学本身是有机结合的，在计算机算法中的许多结构可以看见数学的影子。</p>
<h3 id="差分法">差分法
</h3><p>差分法一般用于减小一维数组的运算量，假设这里有一个长度为n的数组a，那么我们建立一个数组diff_a用于记录a[i]与a[i+1]的差值，这个差值本身就是差分。</p>
<p>例如这里有一个非常长的数组a，我们要在a[x]到a[y] (x于y之间的距离也非常长) ，我们要对这一堆数据进行相同的操作，例如加减赋值，在这里我们就以加值为例。因为a[i]可以用diff[i-1]到diff[i]+a[1]的累加和表示，所以当我们为diff[i-1]加上一个值后，在a[i]本身与之后所有用差分还原的值均加上了这个值，反之可以在a[i]本身与之后减去这个值。</p>
<p>利用这一点，我们便可以在diff[x-1]处加上这个值，在diff[y-1]处减去这个值，以完成在a[x]到a[y]处的加值操作。</p>
<p><strong>以下是洛谷例题示例：</strong></p>
<p>待会写。</p>
<h3 id="前缀法">前缀法
</h3><p>与差分法类似，前缀法旨在用前n项累加的和表示数组，即<code>a[n] = sum_a[a] - sum_a[a-1]</code></p>
<p>基于一维数组的前缀和主要应用场景是可以在O(1)情况下求出任何区间内的和。</p>

</section>


    <footer class="article-footer">
    

    
    <section class="article-copyright">
        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-copyright" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <path d="M14.5 9a3.5 4 0 1 0 0 6" />
</svg>



        <span>Licensed under CC BY-NC-SA 4.0</span>
    </section>
    </footer>


    
</article>

    

    

<aside class="related-content--wrapper">
    <h2 class="section-title">相关文章</h2>
    <div class="related-content">
        <div class="flex article-list--tile">
            
                
<article class="has-image">
    <a href="/p/c-/">
        
        
            <div class="article-image">
                
                    <img src="/images/code1.jpg" loading="lazy" data-key="c&#43;&#43;" data-hash="/images/code1.jpg"/>
                
            </div>
        

        <div class="article-details">
            <h2 class="article-title">C&#43;&#43;语法笔记</h2>
        </div>
    </a>
</article>

            
                
<article class="has-image">
    <a href="/p/wdsj/">
        
        
            <div class="article-image">
                
                    <img src="/images/plc.png" loading="lazy" data-key="wdsj" data-hash="/images/plc.png"/>
                
            </div>
        

        <div class="article-details">
            <h2 class="article-title">我的世界JAVA版非局域网远程联机教程</h2>
        </div>
    </a>
</article>

            
        </div>
    </div>
</aside>

     
    
        
    <div class="disqus-container">
    <div id="disqus_thread"></div>
<script>
    window.disqus_config = function () {
    
    
    
    };
    (function() {
        if (["localhost", "127.0.0.1"].indexOf(window.location.hostname) != -1) {
            document.getElementById('disqus_thread').innerHTML = 'Disqus comments not available by default when the website is previewed locally.';
            return;
        }
        var d = document, s = d.createElement('script'); s.async = true;
        s.src = '//' + "hugo-theme-stack" + '.disqus.com/embed.js';
        s.setAttribute('data-timestamp', +new Date());
        (d.head || d.body).appendChild(s);
    })();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="https://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
</div>

<style>
    .disqus-container {
        background-color: var(--card-background);
        border-radius: var(--card-border-radius);
        box-shadow: var(--shadow-l1);
        padding: var(--card-padding);
    }
</style>

<script>
    window.addEventListener('onColorSchemeChange', (e) => {
        if (typeof DISQUS == 'object') {
            DISQUS.reset({
                reload: true
            });
        }
    })
</script>

    

    <footer class="site-footer">
    <section class="copyright">
        &copy; 
        
        2024 VenKing_Ryao-HEUN
    </section>
    
    <section class="powerby">
        使用 <a href="https://gohugo.io/" target="_blank" rel="noopener">Hugo</a> 构建 <br />
        主题 <b><a href="https://github.com/CaiJimmy/hugo-theme-stack" target="_blank" rel="noopener" data-version="3.29.0">Stack</a></b> 由 <a href="https://jimmycai.com" target="_blank" rel="noopener">Jimmy</a> 设计
    </section>
</footer>


    
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    
    <div class="pswp__bg"></div>

    
    <div class="pswp__scroll-wrap">

        
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                
                
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo="crossorigin="anonymous"
                defer
                >
            </script><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU="crossorigin="anonymous"
                defer
                >
            </script><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.min.css"crossorigin="anonymous"
            ><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.css"crossorigin="anonymous"
            >

            </main>
        </div>
        <script 
                src="https://cdn.jsdelivr.net/npm/node-vibrant@3.1.6/dist/vibrant.min.js"integrity="sha256-awcR2jno4kI5X0zL8ex0vi2z&#43;KMkF24hUW8WePSA9HM="crossorigin="anonymous"
                
                >
            </script><script type="text/javascript" src="/ts/main.fe40349e407ba5b8d0df08d300ffc38d0d30eed264b452958879f7cb3a13a7ed.js" defer></script>
<script>
    (function () {
        const customFont = document.createElement('link');
        customFont.href = "https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap";

        customFont.type = "text/css";
        customFont.rel = "stylesheet";

        document.head.appendChild(customFont);
    }());
</script>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css">
<div id="aplayer"></div>
<script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script>

<script>
const ap = new APlayer({
    container: document.getElementById('aplayer'),
    audio: []
});
</script>

    </body>
</html>
